<?php
/**
 * @title 208. 实现 Trie (前缀树) - 剪枝
 * @author start2004
 */

// ini_set("memory_limit", "128M");

class Trie {
    /**
     * Initialize your data structure here.
     */
    function __construct() {
        $this->hashs = [];
        $this->prefixs = [];
    }

    /**
     * Inserts a word into the trie.
     * @param String $word
     * @return NULL
     */
    function insert($word) {
        if(!isset($this->hashs[$word])){
            $this->hashs[$word] = 1;

            /**
             * @since 2020-08-17 缓存所有前缀头
             */
            $prefix = $word;
            for($i=strlen($word)-1; $i>=0; $i--){
                if(isset($this->prefixs[$prefix])){
                    break;
                } else {
                    $this->prefixs[$prefix] = 1;
                }
                $prefix = substr($prefix, 0, -1);
            }
        } else {}
    }

    /**
     * Returns if the word is in the trie.
     * @param String $word
     * @return Boolean
     */
    function search($word) {
        return isset($this->hashs[$word]);
    }

    /**
     * Returns if there is any word in the trie that starts with the given prefix.
     * @param String $prefix
     * @return Boolean
     */
    function startsWith($prefix) {
        return isset($this->prefixs[$prefix]);
    }
}



/**
 * @url http://127.0.0.1/leetcode/202008/2020.08.17_7.php
 */
$datas = [
    [
        ["Trie","insert","search","search","startsWith","insert","search"],
        [[],["apple"],["apple"],["app"],["app"],["app"],["app"]],
    ],
    [
        ["Trie","insert","search","search","startsWith","startsWith"],
        [[],["ab"],["a"],["ab"],["a"],["ab"]],
    ],
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    $obj = new Trie();

    for ($i=1; $i<count($data[0]); $i++){
        $result = $obj->$data[0][$i]($data[1][$i][0]);

        echo $data[0][$i] ."(\"". $data[1][$i][0] ."\") ";
        if($result === true){
            echo "True";
        } elseif($result === false) {
            echo "False";
        } else {
            echo "Null";
        }
        echo PHP_EOL;
    }

    echo str_repeat(PHP_EOL, 3);
}
$xhprof->end();
